package com.zdp.leetcodeMiddle;


import com.zdp.util.ListNode;

import java.util.HashSet;
import java.util.Set;

/*
* 题目描述：
* 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
* 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以使用 O(1) 空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
* */
public class 环形链表II_142 {

    /*
    * 解题思路：  要求： 返回链表环的第一个节点 无环 返回 null
    *  其实就是判断环 ----> 判断环 可以使用 HashMap（Set） 出现重复节点时，说明有环
    * 第一个出现的重复节点 ---> 入环点
    *  或者使用快慢指针  当 快慢指针相遇时， 使用一个ptr指针指向链表头部 ，当ptr和 slow 相遇时
    *  就是入环口
    * */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null){
            slow = slow.next;
            // 慢指针 走一步 快指针 走两步
            if(fast.next != null){ // 防止空指针异常
                fast = fast.next.next;
            }else{
                return null;
            }
            // 如果 快慢指针相遇 说明有环
            if(slow == fast){
                ListNode ptr = head;
                // ptr 和 slow 一起 后移 直到相遇
                while(ptr !=slow){
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }

        }
        // 如果 fast == null ---> 说明无环 返回null
        return null;
    }

    /*
    * 利用Set求解
    * */
    public ListNode detectCycle1(ListNode head) {
        Set<ListNode> only = new HashSet<>();
        ListNode p = head;
        while(p!=null){
            if(!only.contains(p)){
                only.add(p);
                p = p.next;
            }else{
                return p;
            }
        }
        return null;
    }
}
